Kirby-Paris hydra
The Kirby-Paris hydra game is a one-player game played on a tree that can last a very large number of turns. It gives rise to a function \(\text{Hydra}(n)\) that eventually dominates all recursive functions which are provably total in Peano arithmetic, and is itself provably total in PA + "\(\varepsilon_0\) is well-ordered." The game is closely related to Beklemishev's worms. Rules The game is played as follows: * We start with a finite rooted tree \(T\). Call its root \(r\). * Jonathan picks a leaf vertex of the tree and a natural number \(n\). Call the leaf \(a\) and its parent \(b\): *# \(a\) is deleted from T. *# If \(b = r\), nothing happens. Otherwise, let \(c\) be the parent of \(b\). Consider the subtree consisting of \(b\) and all its children; copy this subtree \(n\) times. Attach all these copies to \(c\). This can be expressed equivalently using strings of parentheses: * Start with a finite sequence of matched parentheses such as (()(()(())((())))). * Pick an empty pair () and a natural number \(n\). *# Delete it. *# If its parent is not the outermost pair, take its parent and append \(n\) copies of it. For example, at step 3 we can transform (()(()())) into (()(())(())(())(())). Jonathan keeps picking leaves and \(n\)'s and chopping off hydra heads. He wins when the hydra is reduced to a root node. Hydra theorem We define a strategy on \(T\) as a sequence of leaves and values of \(n\) that continues as long as the game does. A winning strategy is one that eventually defeats the hydra, and a losing strategy is one that does not. Some strategies are obviously winning strategies. Repeatedly setting \(n = 0\) ensures that the hydra never grows back, for instance. But many strategies (especially for large \(n\)) can cause hydras to grow very rapidly, raising the question: can Jonathan ever lose by allowing the hydra to grow indefinitely? Kirby and Paris showed the answer is no — Jonathan always wins, and there are no losing strategies for any hydra. This fact is called the hydra theorem, and it is unprovable in Peano arithmetic. We will recreate a sketch of their proof of the theorem: Proof: We assign an ordinal to each possible tree, defining () = 0 and (H1H2...H''n'') = \(\omega^{H_1} + \omega^{H_2} + \ldots + \omega^{H_n}\) where \(H_1 \geq H_2 \geq \ldots \geq H_n\). (This ignores the orders of nodes, but order does not affect the hydra theorem.) It can be shown that removing a leaf strictly decreases the hydra \(H\) regardless of the value of \(n\): * If the leaf node we select is a child of the root node, the result is \(H - 1\), which is strictly smaller than \(H\). * If the leaf node we select is a child of node \(J = \omega^{K+1}\), then chopping it results in \(\omega^Kn\), which is strictly smaller than \(J\) for finite \(n\). Since the hydra's value always decreases, its ordinal will reach 0 in a finite amount of time. This strategy is useful for proving the termination of Friedmanesque computable one-player games such as the Buchholz hydra. It can also be applied to Goodstein sequences, although less elegantly. Hydra function Often, the number of steps required to defeat the hydra is very large. Since there are so many parameters at work here, we will simplify things using a few conventions: * Each hydra is a path of length \(k\), that is, a chain of \(k + 1\) nodes. * The strategy always picks the rightmost node using \(n = 1\), then \(n = 2\), then \(n = 3\), etc. until the game ends. Using these hydras and strategies, define \(\text{Hydra}(k)\) as the number of turns needed to win the game. Then \begin{eqnarray*} \text{Hydra}(0) &=& 0\\ \text{Hydra}(1) &=& 1\\ \text{Hydra}(2) &=& 3\\ \text{Hydra}(3) &=& 37\\ \text{Hydra}(4) &>& f_{\omega*2 +4}(5) \approx \{5,5,4,3\} >> \text{Graham's number}\\ \text{Hydra}(5) &>& f_{\omega^{\omega*2 + 4}}(5) \approx \{5,5 (1) (1) 5,5,5,5,5\}\\ \end{eqnarray*} The computation of \(\text{Hydra}(3)\) is shown to the right. In general, \(f_{\omega^{\omega^{\cdots^{\omega2+4}}}}(6) > \text{Hydra}(n) > f_{\omega^{\omega^{\cdots^{\omega2+4}}}}(5) > X \uparrow\uparrow (n-4) \&\ 5\), where are \(n-3\) copies of \(\omega\) in each tower. \(\text{Hydra}(n)\) eventually dominates all functions provably recursive in Peano arithmetic, and it can be approximated with the function \(f_{\varepsilon_0}\). In particular, \(\text{Hydra} >^* f_\alpha\) for all \(\alpha < \varepsilon_0\), but \(\text{Hydra} <^* f_{\varepsilon_0 + 1}\). This puts the hydra function on par with Goodstein sequences and tetrational BEAF arrays. External links *Kirby, L.; Paris, J. (1982), "Accessible independence results for Peano arithmetic", Bulletin of the London Mathematical Society 14: 285–293. *Weisstein, Eric W., "Goodstein Sequence", MathWorld. *Some elements of a proof that Goodstein's theorem is not a theorem of PA, from an undergraduate thesis by Justin T Miller *A Classification of non stanard models of Peano Arithmetic by Goodstein's theorem - Thesis by Dan Kaplan, Franklan and Marshall College Library *Definitions of Goodstein sequences in the programming languages Ruby and Haskell, as well as a large-scale plot *Goodstein Sequences: The Power of a Detour via Infinity - good exposition with illustrations of Goodstein Sequences and the hydra game. See also ja:ヒドラゲーム Category:Functions Category:Games Category:Combinatorics